lang/C/sorting.and.searching.cormen.algo/Introduction to Algorithms, Third Edition/code/quilist.c

   1 /* quicksort, for linked lists */
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 typedef int T;                  /* type of item to be sorted */
   7
   8 typedef struct listTag {        /* typical node to be sorted */
   9     struct listTag *next;
  10     struct listTag *prev;
  11     T data;
  12 } listNode;
  13
  14 #define compLT(a,b) (a < b)
  15 #define compGT(a,b) (a > b)
  16
  17 listNode *partition(listNode *lb, listNode *rb) {
  18     T t, pivot;
  19     listNode *i, *j;
  20     int done;           /* record if pointers cross (means we're done!) */
  21
  22    /********************************************************
  23     * partition list [lb..rb], and return pointer to pivot *
  24     ********************************************************/
  25
  26     /* select a pivot */
  27     pivot = lb->data;
  28     done = 0;
  29
  30     /* scan from both ends, swapping when needed */
  31     /* care must be taken not to address outside [lb..rb] with pointers */
  32     i = lb; j = rb;
  33     while(1) {
  34         while (compGT(j->data, pivot)) {
  35             j = j->prev;
  36             if (i == j) done = 1;
  37         }
  38         if (done) return j;
  39         while (compLT(i->data, pivot)) {
  40             i = i->next;
  41             if (i == j) done = 1;
  42         }
  43         if (done) return j;
  44
  45         /* swap i, j */
  46         t = i->data;
  47         i->data = j->data;
  48         j->data = t;
  49
  50         /* examine next element */
  51         j = j->prev;
  52         if (i == j) done = 1;
  53         i = i->next;
  54         if (i == j) done = 1;
  55     }
  56 }
  57
  58 void quickSort(listNode *lb, listNode *rb) {
  59     listNode *m;
  60
  61    /************************
  62     *  sort list [lb..rb]  *
  63     ************************/
  64
  65     if (lb == rb) return;
  66
  67     m = partition(lb, rb);
  68
  69     if (m != lb) quickSort(lb, m);              /* sort left side */
  70     if (m != rb) quickSort(m->next, rb);        /* sort right side */
  71 }
  72
  73 int main(int argc, char *argv[]) {
  74     /* command-line:
  75      *
  76      *   quilist maxnum
  77      *
  78      *   quilist 2000
  79      *       sorts 2000 records
  80      *
  81      */
  82
  83     listNode *p0;
  84     int maxnum, i;
  85
  86     maxnum = atoi(argv[1]);
  87     if ((p0 = malloc(maxnum * sizeof(listNode))) == 0) {
  88         fprintf (stderr, "insufficient memory (a)\n");
  89         exit(1);
  90     }
  91
  92     /* initialize list */
  93     srand(1);
  94     for (i = 0; i < maxnum; i++) {
  95         p0[i].next = p0 + i + 1;
  96         p0[i].prev = p0 + i - 1;
  97         p0[i].data = rand();
  98     }
  99
 100     quickSort(p0, p0 + maxnum-1);
 101
 102     return 0;
 103 }